package com.cuz.for2024;

import java.lang.reflect.Array;
import java.util.Arrays;

public class T31 {
    public void nextPermutation(int[] nums) {

        // 1 3 6 5 4 2 1
        // 1 4 6 5 3 2 1
        // 1 4 1 2 3 4 5

        // 6 5 4 2 1
        int index = nums.length - 2;
        while (index >= 0) {
            // 1 3 6 5 4 2 1
            // index =2
            if (nums[index] < nums[index + 1]) {
                break;
            }
            index--;
        }
        if (index < 0) {
            int l = 0;
            int r = nums.length - 1;
            while (l < r) {
                swap(nums, l, r);
                l++;
                r--;
            }
            return;
        }
        int target = nums[index];
        for (int i = nums.length - 1; i >= index + 1; i--) {
            if (nums[i] > target) {
                swap(nums, i, index);
                break;
            }
        }
        // 1 4 6 5 3 2 1
        int l = index + 1;
        int r = nums.length - 1;
        while (l < r) {
            swap(nums, l, r);
            l++;
            r--;
        }
        return;
    }

    private void swap(int[] nums, int l, int r) {
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }

    public static void main(String[] args) {
        int[] a = {3, 2, 1,3};
        new T31().nextPermutation(a);
        System.out.println(Arrays.toString(a));
    }
}
